Markovian arrival processes

In queueing theory, Markovian arrival processes are used to model the arrival of customers to a queue.

Some of the most common include the Poisson process, Markov arrival process and the batch Markov arrival process.

Contents

Background

Markovian arrival processes have two processes. A continuous-time Markov process j(t), a Markov process which is generated by a generator or rate matrix, Q. The other process is a counting process N(t), which has state space \mathbb{N}_{0}:=\mathbb{N}\cup\{0\} (where \mathbb{N} is the set of all natural numbers). N(t) increases every time there is a transition in j(t) that is marked.

Poisson process

The Poisson arrival process or Poisson process counts the number of arrivals, each of which has an exponentially distributed time between arrival. In the most general case this can be represented by the rate matrix,

Q=\left[\begin{matrix} -\lambda_{0}&\lambda_{0}&0&0&\dots\\ 0&-\lambda_{1}&\lambda_{1}&0&\dots\\ 0&0&-\lambda_{2}&\lambda_{2}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .

In the homogeneous case this is more simply,

Q=\left[\begin{matrix} -\lambda&\lambda&0&0&\dots\\ 0&-\lambda&\lambda&0&\dots\\ 0&0&-\lambda&\lambda&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .

Here every transition is marked.

Markov arrival process

The Markov arrival process (MAP) is a generalization of the Poisson process by having non-exponential distribution sojourn between arrivals. The homogeneous case has rate matrix,

Q=\left[\begin{matrix} D_{0}&D_{1}&0&0&\dots\\ 0&D_{0}&D_{1}&0&\dots\\ 0&0&D_{0}&D_{1}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .

An arrival is seen every time a transition occurs that increases the level (a marked transition), e.g. a transition in the D_{1} sub-matrix. Sub-matrices D_{0} and D_{1} have elements of \lambda_{i,j}, the rate of a Poisson process, such that,

0\leq [D_{1}]_{i,j}<\infty
0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j
[D_{0}]_{i,i}<0\;

and

(D_{0}%2BD_{1})\boldsymbol{1}=\boldsymbol{0}

There are several special cases of the Markov arrival process.

Markov-modulated Poisson process

The Markov-modulated Poisson process or MMPP where m Poisson processes are switched between by an underlying Markov process. If each of the m Poisson processes has rate \lambda_{i} and the underlying process is generated by a m\times m generator matrix R, then in the MAP representation,

D_{1} = \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}

a diagonal matrix of the rates of the Poisson process, and

D_{0}=R-D_{1}

Phase-type renewal process

The phase-type renewal process is a Markov arrival process with phase-type distributed sojourn between arrivals. For example if an arrival process has an interarrival time distribution PH(\boldsymbol{\alpha},S) with an exit vector denoted \boldsymbol{S}^{0}=-S\boldsymbol{1}, the arrival process has generator matrix,

Q=\left[\begin{matrix} S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&0&\dots\\ 0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&\dots\\ 0&0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&\dots\\ \vdots&\vdots&\ddots&\ddots&\ddots\\ \end{matrix}\right]

Batch Markov arrival process

The batch Markovian arrival process (BMAP) is a generalisation of the Markovian arrival process by having arrivals of size greater than one. The homogeneous case has rate matrix,

Q=\left[\begin{matrix} D_{0}&D_{1}&D_{2}&D_{3}&\dots\\ 0&D_{0}&D_{1}&D_{2}&\dots\\ 0&0&D_{0}&D_{1}&\dots\\ \vdots & \vdots & \ddots & \ddots & \ddots \end{matrix}\right]\; .

An arrival of size k occurs every time a transition occurs in the sub-matrix D_{k}. Sub-matrices D_{k} have elements of \lambda_{i,j}, the rate of a Poisson process, such that,

0\leq [D_{k}]_{i,j}<\infty\;\;\;\; 1\leq k
0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j
[D_{0}]_{i,i}<0\;

and

\sum^{\infty}_{k=0}D_{k}\boldsymbol{1}=\boldsymbol{0}

References